#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/5/16 11:36|11:36
# @Author  : yangdingyi
# @File    : 25. K 个一组翻转链表.2020-05-16
# @Software: PyCharm

from typing import List


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # print(display(head))

        def reverse(h: ListNode) -> (ListNode, ListNode):
            if not h:
                return None, None
            q = h
            p = h.next
            while p:
                x = p.next
                p.next = q
                q = p
                p = x
            h.next = None
            return q, h

        i = 0
        ni = head
        hh = None
        h1 = head
        while ni:
            if i % k == k - 1:
                nn = ni.next
                ni.next = None
                u, e = reverse(h1)
                if hh:
                    hh.next = u
                else:
                    head = u
                hh = e
                h1 = nn
                ni = nn
                i = 0
            else:
                ni = ni.next
                i = (i + 1) % k
        if h1:
            # hh.next = reverse(h1)[0]
            hh.next = h1
        return head


def display(h: ListNode) -> str:
    ret = ''
    while h:
        ret += f'{h.val}'
        if h.next:
            ret += ' -> '
        h = h.next
    return ret


def make_list(num_list: List) -> ListNode:
    head = None
    tail = None
    for i in range(len(num_list)):
        if not head:
            head = ListNode(num_list[i])
            tail = head
        else:
            tail.next = ListNode(num_list[i])
            tail = tail.next
    return head


solve = Solution()

nums = [1, 2, 3, 4, 5]
k = 3
_nums = make_list(nums)
print(display(_nums), k)
print(display(solve.reverseKGroup(_nums, k)))





